package SubSequence.Medium;

import java.util.HashMap;

public class LC0560 {
    public int subarraySum(int[] nums, int k) {
        int N = nums.length;
        int[] sum = new int[N]; // [0,i]范围内数字的和
        int tmp = 0;
        for (int i = 0; i < N; i++) {
            tmp += nums[i];
            sum[i] = tmp;
        }

        int ret = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                if (i == 0) {
                    if (sum[j] == k) ret++;
                }
                else {
                    if (sum[j] - sum[i - 1] == k) ret++;
                }
            }
        }

        return ret;
    }

    /**
     * 我们并不关心子串的具体位置，而只关心子串的个数。利用一个哈希表存储<前缀和，出现次数>的对。每次计算出一个前缀和sum，都检查sum-k的出现次数，
     * 并使相应的value增加1。
     * 先检查出现次数再增1的顺序，可以避免k=0时的错误。
     */
    public int subarraySumWithHash(int[] nums, int k) {
        int N = nums.length;

        HashMap<Integer, Integer> sumNumMap = new HashMap<>();
        sumNumMap.put(0, 1);
        int tmp = 0, ret = 0;
        for (int i = 0; i < N; i++) {
            tmp += nums[i];
            ret += sumNumMap.getOrDefault(tmp - k, 0);
            sumNumMap.put(tmp, sumNumMap.getOrDefault(tmp, 0) + 1);
        }

        return ret;
    }
}
